import java.util.*;

public class Test1 {
    //利用Hashmap来做
    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        System.out.println(topKFrequent(words, 2));
    }
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (String s:words) {
            if (map.get(s) == null){
                map.put(s,1);
            }else {
                map.put(s,map.get(s) + 1);
            }
        }
        //利用小根堆来获取前K个出现次数最多的高频元素
        PriorityQueue<Map.Entry<String,Integer>> minheap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            //指定比较器，使放入的元素根据比较规则进行比较
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        //往小根堆里放元素
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
            if(minheap.size() < k){
                //没满就继续往里面放
                minheap.add(entry);
            }else {
                //放满了就用堆顶元素和后继元素进行比较
                Map.Entry<String,Integer> top = minheap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    minheap.poll();
                    minheap.add(entry);
                }else{
                    //要求在频率相同的情况下按字典序排序
                    if(top.getValue().compareTo(entry.getValue()) == 0){
                        //频率相同，字典序大的元素被弹出
                        if(top.getKey().compareTo(entry.getKey()) > 0){
                            minheap.poll();
                            minheap.add(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ret.add(minheap.poll().getKey());
        }
        Collections.reverse(ret);
        return  ret;
    }
}
